/*
104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
 */
package LC0104;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// 迭代法，自己完成的
class Solution1 {
    public int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }

        int count = 1;

        count = nextNode(root.left, root.right, count);

        return count;
    }

    public int nextNode (TreeNode left, TreeNode right, int count){
        // 终止条件
        if (left == null && right == null){
            return count;
        }

        if (left == null){
            count++;
            return nextNode(right.left, right.right, count);
        }

        if (right == null){
            count++;
            return nextNode(left.left, left.right, count);
        }

        count++;
        return Math.max(nextNode(left.left, left.right, count), nextNode(right.left, right.right, count)) ;
    }
}
